//https://leetcode.cn/problems/number-of-longest-increasing-subsequence/submissions/579275375/
class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> length(n, 1);
        vector<int> count(n, 1);
        int max1 = 1;
        for (int i = 1; i < n; ++i)
        {
            for (int j = i - 1; j >= 0; --j)
            {
                if (nums[j] < nums[i])
                {
                    if (length[j] + 1 > length[i])
                    {
                        length[i] = length[j] + 1;
                        count[i] = count[j];
                    }
                    else if (length[j] + 1 == length[i])
                    {
                        count[i] += count[j];
                    }
                }
                max1 = max(max1, length[i]);
            }
        }
        int ret = 0;
        for (int i = 0; i < n; ++i)
        {
            if (length[i] == max1)
                ret += count[i];
        }
        return ret;
    }
};